﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };
        int left = 0, right = 0, len = 0;
        while (right < s.size())
        {
            // 进⼊窗⼝
            hash[s[right]]++;
            // 判断
            while (hash[s[right]] > 1)
            {
                // 出窗⼝
                hash[s[left]]--;
                left++;
            }
            // 更新结果
            len = max(len, right - left + 1);
            // 让下⼀个元素进⼊窗⼝
            right++;
        }

        return len;
    }
};

// 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        // 转换为0的个数不超过k
        int ret = 0, count = 0;
        for (int left = 0, right = 0; right < nums.size(); right++)
        {
            //为0就加加计数
            if (nums[right] == 0)
                count++;
            //左边一直走，直到0的个数小于k
            while (count > k)
            {
                if (nums[left++] == 0)
                    count--;
            }
            ret = max(ret, right - left + 1);
        }

        return ret;
    }
};

//给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

//函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，
//所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 使用双指针的思想，利用单调性
        int left = 0, right = numbers.size() - 1;
        while (left < right)
        {
            int sum = numbers[left] + numbers[right];
            // 比目标值小，那么右边的任何一个数和左边的加起来都比目标值小，所以左边的数应该增大
            if (sum < target)
                left++;
            // 比目标值大，那么左边的任何一个数和右边的数加起来都比目标值大，那么右边的数应该减小
            else if (sum > target)
                right--;
            else
                return { left,right };
        }

        return { -1,-1 };
    }

};


//给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

//如果存在出现超过一半的元素，则排序后该元素一定在数组的最中间
//1. 利用STL提供的sort方法直接排序
//2. 找到最中间的元素，即：numbers.size() / 2
//3. 统计该元素出现的总次数，如果超过一半输出该元素，否则输出0
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        if (numbers.empty())
            return 0;
        // 排序，取数组中间那个数
        sort(numbers.begin(), numbers.end());
        int middle = numbers[numbers.size() / 2];
        // 出现次数
        int count = 0;
        for (auto e : numbers)
        {
            if (e == middle)
                count++;
        }
        return (count > numbers.size() / 2) ? middle : 0;
    }
};


//使用map统计每个数字出现的次数，如果哪个数字出现的次数超过了元素总个数的一半，则找到了该数据。
//时间复杂度：O(NlogN)
class Solution {
public:
    
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        //map 记录出现次数
        map<int, int> _map;
        int count = 0;
        // 统计numbers[i]数组出现的次数
        for (auto e : numbers)
        {
            count = ++_map[e];
            // 如果该数字出现次数超过了数组总大小的一半，则找到了
            if (count > numbers.size() / 2)
                return e;
        }

        return 0;

    }
};

//设计一个计数count，记录x数据出现的次数。遍历数组，拿到numbers[i]后，进行如下操作：
//1. 如果count等于0，表明该元素第一次出现，使用x记录该元素，并将count设置为1
//2. 否则：如果numbers[i] == x，count++；否则count--
//上述操作结束后，x中标记的元素可能是出现次数刚好超过一般的元素。最后在遍历一遍次数，确认x是否真
//的超过一半。
//时间复杂度：O(N)

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        if (numbers.empty())
            return 0;
        int count = 0;
        int x = numbers[0];
        for (size_t i = 0; i < numbers.size(); ++i)
        {
            if (count == 0)
            {
                x = numbers[i];
                count = 1;
            }
            else
            {
                if (x == numbers[i])
                    count++;
                else
                    count--;
            }
        }
        count = 0;
        for (auto e : numbers)
        {
            if (e == x)
                count++;
            if (count > numbers.size() / 2)
                return x;
        }
        return 0;
    }
};
int main()
{
	return 0;
}